package top.datacluster.basic.algorithm.leetcode.stack;

import java.util.Stack;

/**
 * 856. 括号的分数
 * 给定一个平衡括号字符串 S，按下述规则计算该字符串的分数：
 *
 * () 得 1 分。
 * AB 得 A + B 分，其中 A 和 B 是平衡括号字符串。
 * (A) 得 2 * A 分，其中 A 是平衡括号字符串。
 *
 *
 * 示例 1：
 *
 * 输入： "()"
 * 输出： 1
 * 示例 2：
 *
 * 输入： "(())"
 * 输出： 2
 * 示例 3：
 *
 * 输入： "()()"
 * 输出： 2
 * 示例 4：
 *
 * 输入： "(()(()))"
 * 输出： 6
 *
 *
 * 提示：
 *
 * S 是平衡括号字符串，且只含有 ( 和 ) 。
 * 2 <= S.length <= 50
 */
public class LeetCdoe856 {

    public int scoreOfParentheses(String S) {
        Stack<Node> stack = new Stack();

        for (int i = 0; i < S.length(); i++){
            Node node = new Node();

            if (S.charAt(i) == '('){
                node.type = 0;
                stack.push(node);
                continue;
            }
            if (S.charAt(i) == ')'){
                int temp = 0;
                while (stack.peek().type != 0){
                    temp += stack.pop().data;
                }
                stack.pop();
                if (temp == 0){
                    node.type = 1;
                    node.data = 1;
                }else{
                    node.type = 1;
                    node.data = temp * 2;
                }
                stack.push(node);
                continue;
            }
        }
        int result = 0;
        while (!stack.isEmpty()){
            result += stack.pop().data;
        }
        return result;

    }
}


class Node{
    int data;
    int type;
}